package org.example.algorithm.graph;

import java.util.LinkedList;
import java.util.Queue;

public class NumIslandsSolution {
    private int islandCount = 0;

    public static void main(String[] args) {
        char[][] grid = {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};
        NumIslandsSolution solution = new NumIslandsSolution();
        int res = solution.numIslands(grid);
        System.out.println(res);
    }

    public void bfs(char[][] grid, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        while (!queue.isEmpty()) {
            int[] item = queue.poll();
            int r = item[0];
            int c = item[1];
            if (r<0 || r>=grid.length || c<0 || c>=grid[0].length || grid[r][c] == '0') {
                continue;
            }
            queue.offer(new int[]{r-1, c});
            queue.offer(new int[]{r+1, c});
            queue.offer(new int[]{r, c-1});
            queue.offer(new int[]{r, c+1});
            grid[r][c] = '0';
        }
    }

    public int numIslands(char[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        for (int i=0;i<row;i++) {
            for (int j=0;j<column;j++) {
                if (grid[i][j] == '0') {
                    continue;
                }
                //dfs(grid, i, j);
                bfs(grid, i, j);
                islandCount++;
            }
        }
        return islandCount;
    }

    public void dfs(char[][] grid, int i, int j) {
        if (i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i, j+1);
        dfs(grid, i-1, j);
        dfs(grid, i, j - 1);
    }
}
